package algorithm;

import java.util.Arrays;

public class T00931 {
    public static void main(String[] args) {
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        System.out.println(new Solution().minFallingPathSum(matrix));
    }

    static class Solution {
        private static final int MAX_VAL = 99999;
        private static final int CACHE_DEF_VAL = 66666;
        private int[][] cache;

        public int minFallingPathSum(int[][] matrix) {
            int n = matrix.length;
            cache = new int[n][n];
            for (int[] c : cache) {
                Arrays.fill(c, CACHE_DEF_VAL);
            }
            int res = MAX_VAL;
            for (int i = 0; i < n; i++) {
                res = Math.min(dp(matrix, n - 1, i), res);
            }
            return res;
        }

        public int dp(int[][] matrix, int i, int j) {
            if (i < 0 || i >= matrix.length || j < 0 || j >= matrix.length) {
                return MAX_VAL;
            }
            if (i == 0) return matrix[i][j];
            if (cache[i][j] != CACHE_DEF_VAL) {
                return cache[i][j];
            }
            int dpVal = matrix[i][j] + min(dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1));
            cache[i][j] = dpVal;
            return dpVal;
        }

        private int min(int dp, int dp1, int dp2) {
            return Math.min(dp, Math.min(dp1, dp2));
        }
    }
}
